#include "BTreeNode.h"

using namespace std;

BTLeafNode::BTLeafNode()
{
  m_keyCount = 0;
  m_MAXKEYCOUNT = 85; /* equation: (1024-4)/(4+8) */
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::read(PageId pid, const PageFile& pf)
{
  return pf.read (pid, buffer);
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf)
{
  return pf.write (pid, buffer);
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount()
{
  return m_keyCount;
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{
  if(key < 0)
  { return RC_INVALID_ATTRIBUTE;  }
  
  int temp;
  int offset;
  
  if(m_keyCount < m_MAXKEYCOUNT)
  {
    /* Empty node */
    if(m_keyCount == 0)
    {
      memcpy(buffer, &rid, sizeof(RecordId));
      memcpy(buffer+8, &key, sizeof(int));
      m_keyCount++;
      return 0; 
    }
    
    for(int i = 0; i < m_keyCount; i++)
    {
      memcpy(&temp, buffer+(i*12)+8, sizeof(int));
      
      /* If parameter key is smaller than some of the keys stored in node */
      if(key < temp)
      {
        offset = (m_keyCount*12)-(i*12);
        memmove(buffer+(i*12)+12, buffer+(i*12), offset);
        memcpy(buffer+(i*12), &rid, sizeof(RecordId));
        memcpy(buffer+(i*12)+8, &key, sizeof(int));
        m_keyCount++;
        return 0; 
      }
    }
    
    /* If parameter has largest key value */
    memcpy(buffer+(m_keyCount*12), &rid, sizeof(RecordId));
    memcpy(buffer+(m_keyCount*12)+8, &key, sizeof(int));   
    m_keyCount++;
    return 0; 
  }
  /* Error */
  else
  {
    return RC_NODE_FULL;
  }  
}   

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey)
{
  if(key < 0)
  { return RC_INVALID_ATTRIBUTE;  } 
  
  if(sibling.m_keyCount > 0)
  {
    return RC_NODE_FULL;
  }
  
  int temp;
  int os;

	/* Divide buffer into two parts */
	int half = m_keyCount / 2;
	int offset = half*sizeof(key) + half*sizeof(rid);

	/* Start after the first "half" # of keys.
	 * Move the contents of the rest of the buffer, except the pid, to its sibling. */

		memmove(sibling.buffer, (buffer+offset), (1020-offset));

		/* If # keys was even, no problem;
		 * if odd, account for one less key-rid pair in sibling */
		if(m_keyCount % 2 == 0) { sibling.m_keyCount += half; }
		else { sibling.m_keyCount += half+1; }
		
		m_keyCount = half;

		/* Add new key-rid pair either to current node or sibling node */
    for(int i = 0; i < m_keyCount; i++)
    {
      memcpy(&temp, buffer+(i*12)+8, sizeof(int));
      
      /* If parameter key is smaller than some of the keys stored in node */
      if(key < temp)
      {
        os = (m_keyCount*12)-(i*12);
        memmove(buffer+(i*12)+12, buffer+(i*12), os);
        memcpy(buffer+(i*12), &rid, sizeof(RecordId));
        memcpy(buffer+(i*12)+8, &key, sizeof(int));
        m_keyCount++;
        goto exit_insert; 
      }
    }   
 
      //Store key,rid in sibling node
      for(int i = 0; i < sibling.m_keyCount; i++)
      {
        memcpy(&temp, sibling.buffer+(i*12), sizeof(int));
        
        /* If parameter key is smaller than some of the keys stored in node */
        if(key < temp)
        {
          os = (sibling.m_keyCount*12)-(i*12);
          memmove(sibling.buffer+(i*12)+12, sibling.buffer+(i*12), os);
          memcpy(sibling.buffer+(i*12), &rid, sizeof(RecordId));
          memcpy(sibling.buffer+(i*12)+8, &key, sizeof(int));
          sibling.m_keyCount++;
          goto exit_insert;  
        }
      }

      /* If parameter has largest key value */
      memcpy(sibling.buffer+(sibling.m_keyCount*12), &rid, sizeof(RecordId));
      memcpy(sibling.buffer+(sibling.m_keyCount*12)+8, &key, sizeof(int));
      sibling.m_keyCount++;
      goto exit_insert;
    
    exit_insert:  
		/* Determine first key in sibling node */
		memcpy(&siblingKey+8, sibling.buffer, sizeof(key));
		return 0;
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{
  if(searchKey < 0)
  { return RC_INVALID_ATTRIBUTE;  }
  
	/* Use this to keep track of whether or not we find a value >= searchKey */
	int star = 0;

	/* Use this to keep track of keyCount */
	int counter = 0;

	/* Loop through the buffer's keys */
	for(int i = 0; i < m_keyCount; i++)
	{
		memcpy(&star, buffer+(i*12)+8, sizeof(int));
		if(star >= searchKey) { goto exit_1; } /* If found, break out of the loop! */
		counter++;
	}
	return RC_NO_SUCH_RECORD;

	exit_1:
	eid = counter;
	return 0;
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{ 
  if(eid < 0)
  { return RC_INVALID_ATTRIBUTE;  }
  
	memcpy(&rid, buffer+(eid*12), sizeof(rid));
  memcpy(&key, buffer+(eid*12)+8, sizeof(key));	
	return 0;
}

/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{
	PageId* pagePtr;
	memcpy(pagePtr, buffer+1020, 4);
	return *pagePtr;
}

/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{
  if(pid < 0)
  { return RC_INVALID_PID;  }
  
	PageId* pagePtr = &pid;
	memcpy(buffer+1020, pagePtr, 4);
	return 0;
}

BTNonLeafNode::BTNonLeafNode()
{
  m_keyCount = 0;
  m_MAXKEYCOUNT = 127; /* equation: (1024-8)/(4+4) */
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{
  return pf.read (pid, buffer);
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{
  return pf.write (pid, buffer);
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount()
{
  return m_keyCount;
}


/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid)
{
  if(key < 0)
  { return RC_INVALID_ATTRIBUTE;  } 
  
  if(pid < 0)
  { return RC_INVALID_PID;  }
  
  int temp;
  int offset;
  
  if(m_keyCount < m_MAXKEYCOUNT)
  {
    /* Empty node */
    if(m_keyCount == 0)
    {
      memcpy(buffer+4, &key, sizeof(int));
      memcpy(buffer+8, &pid, sizeof(PageId));
      m_keyCount++;
      return 0; 
    }
    
    for(int i = 0; i < m_keyCount; i++)
    {
      memcpy(&temp, buffer+4+(i*8), sizeof(int));
      
      /* If parameter key is smaller than some of the keys stored in node */
      if(key < temp)
      {
        offset = (m_keyCount*8)-(i*8);
        memmove(buffer+4+(i*8)+8, buffer+4+(i*8), offset);
        memcpy(buffer+4+(i*8), &key, sizeof(int));
        memcpy(buffer+8+(i*8), &pid, sizeof(PageId));
        m_keyCount++;
        return 0; 
      }
    }
    
    /* If parameter has largest key value */
    memcpy(buffer+4+(m_keyCount*8), &key, sizeof(int));   
    memcpy(buffer+8+(m_keyCount*8), &pid, sizeof(PageId));
    m_keyCount++;
    return 0; 
  }
  /* Error */
  else
  {
    return RC_NODE_FULL;
  }  
}  

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{
  if(key < 0)
  { return RC_INVALID_ATTRIBUTE;  } 
  
  if(pid < 0)
  { return RC_INVALID_PID;  }
  
  if(sibling.m_keyCount > 0)
  {
    return RC_NODE_FULL;
  }
  
  int temp;
  int os;
  
  int half = m_keyCount / 2; /* 63 */
	int offset = half*sizeof(key) + half*sizeof(pid);
	
	memmove(sibling.buffer, (buffer+offset)+4, (1020-offset));
	
  if(m_keyCount % 2 == 0) { sibling.m_keyCount += half; }
  else { sibling.m_keyCount += half+1; }
		
  m_keyCount = half;
  

    
    for(int i = 0; i < m_keyCount; i++)
    {
      memcpy(&temp, buffer+4+(i*8), sizeof(int));
      
      /* If parameter key is smaller than some of the keys stored in node */
      if(key < temp)
      {
        os = (m_keyCount*8)-(i*8);
        memmove(buffer+4+(i*8)+8, buffer+4+(i*8), offset);
        memcpy(buffer+4+(i*8), &key, sizeof(int));
        memcpy(buffer+8+(i*8), &pid, sizeof(PageId));
        m_keyCount++;
        goto insert_exit; 
      }                 
    }
    
    for(int i = 0; i < sibling.m_keyCount; i++)
    {
      memcpy(&temp, sibling.buffer+4+(i*8), sizeof(int));
      
      /* If parameter key is smaller than some of the keys stored in node */
      if(key < temp)
      {
        os = (sibling.m_keyCount*8)-(i*8);
        memmove(sibling.buffer+4+(i*8)+8, sibling.buffer+4+(i*8), os);
        memcpy(sibling.buffer+4+(i*8), &key, sizeof(int));
        memcpy(sibling.buffer+8+(i*8), &pid, sizeof(PageId));
        sibling.m_keyCount++;
        goto insert_exit; 
      }                 
    }
    
    /* If parameter has largest key value */
    memcpy(sibling.buffer+4+(sibling.m_keyCount*8), &key, sizeof(int));   
    memcpy(sibling.buffer+8+(sibling.m_keyCount*8), &pid, sizeof(PageId));
    sibling.m_keyCount++;
    goto insert_exit;
  
  insert_exit:
  /* Push mid-key out (mid-key is always the first key of sibling node) */
  memcpy(&midKey, sibling.buffer, sizeof(int));
  memmove(sibling.buffer, sibling.buffer+4, 1020);
  return 0;
}  

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{
  /* Check for validity of searchKey */
  if(searchKey < 0) { return RC_INVALID_ATTRIBUTE; }
  
  /* Check for validity of pid */
  if(pid < 0) { return RC_INVALID_PID; }

  int* cmp;
  
  /* Find a pid that corresponds to a key less than searchKey */
  for(int i = 0; i < 127; i++) {
    memcpy(cmp, buffer+4+(8*i), 4);
    if(searchKey < *cmp) {
      memcpy(&pid, buffer+(8*i), 4);
      return 0;
    }
  }

  /* Otherwise, find the last pid */
  memcpy(&pid, buffer+1016, 4);
  return 0;
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{
  /* Check for validity of key */
  if(key < 0) { return RC_INVALID_ATTRIBUTE; }
  
  /* Check for validity of pid1
  if(pid1 < 0) { return RC_INVALID_PID; } */
  
  /* Check for validity of pid2 */
  if(pid2 < 0) { return RC_INVALID_PID; }
  
  memcpy(&pid1, buffer, 4);
  memcpy(&key, buffer+4, 4);
  memcpy(&pid2, buffer+8, 4);
  m_keyCount++;
  return 0;
}
